package com.Exer;

public class Solution {
    static final int mod = 1_000_000_007;
    static final int MX = 100100;
    int n;
    char[] p;
    int[] d3 = new int[MX];
    int[] d4 = new int[MX];
    static boolean done = false;
    //2 ~ 9
    private void init(){
        if (done){
            return;
        }
        done = true;
        d3[0] = d4[0] = 1;
        d3[1] = d4[1] = 1;
        d3[2] = d4[2] = 2;
        d3[3] = d4[3] = 4;
        for (int i = 4; i < MX; i++){
            d3[i] = (d3[i - 1]  + d3[i - 2] + d3[i - 3]) % mod;
            d4[i] = (d4[i - 1] + d4[i - 2] + d4[i - 3] + d4[i - 4]) % mod;
        }

    }
    public int countTexts(String pressedKeys) {
        n = pressedKeys.length();
        p = pressedKeys.toCharArray();
        long ans = 1;
        int cnt = 0;
        init();
        for (int i = 0; i < n ; i++){
            cnt ++;
            char t = p[i];
            if (i == n - 1 || p[i] != p[i + 1]){
                ans = ans * (t != '7' && t != '9' ? d3[cnt] : d4[cnt]) % mod;
                cnt = 0;
            }
        }
        return (int)ans;
    }
    public static void main(String[] args) {
        String press = "222222222222222222222222222222222222";
        Solution s = new Solution();
        int ret = s.countTexts(press);
        System.out.println(ret);
    }
}

